1. Field of the Invention
The present invention relates to cryptography and, in particular, to a method and an apparatus for protecting an exponentiation calculation from error attacks by means of the Chinese remainder theorem (CRT).
2. Description of the Related Art
Modular exponentiation is one of the core calculations for various cryptographic algorithms. One example of a widespread cryptographic algorithm is the RSA cryptosystem described, for example, in “Handbook of Applied Cryptography”, Menezes, van Oorschot, Vanstone, CRC Press, 1996, chapter 8.2. The RSA cryptosystem operates as follows. In the encryption, a party B encrypts a message m for another party A. Party A is supposed to decrypt the encrypted message received from B. Initially party B receives the public key from party A. Then party B represents the message to be encrypted as an integer m. Then party B encrypts the message m as follows:c=me mod n   (1)
In the equation (1), m represents the plain-text message. e is the public key. n is the module and is also public. c represents the encrypted message.
Party B now sends the encrypted message c to party A.
For decryption, i.e. to recover the plain-text m from the secret text c, A performs the following calculation:m=cd mod n   (2)
In the equation (2), d represents the private key of party A which is to be protected against attacks.
An RSA signature algorithm is also known in the art. This involves the following procedure. Each entity A initially creates two large prime numbers p and q and then calculates the module n from the product of p and q. As has also been described in chapter 11.3 in the above-mentioned specialist book, a key is generated therefrom, so that each party has a public key comprised of n, i.e. the module, and e, whereas each party additionally has a private key d.
For RSA signature generation and verification, entity A signs a message m. Each entity B is to be able to verify A's signature and to retrieve the message m from the signature.
In the signature generation, entity A initially calculates an integer m′=R(m). Thereafter, entity A conducts the following calculation:s=m′d mod n   (3)wherein s is A's signature for the message m.
To verify the party A's signature and for retrieving the message m, party B must proceed as follows:
First of all, party B must obtain the public key (n, e) from A. Then party B conducts the following calculation:m′=se mod n   (4)
In the equation (4) e is A's public key.
Party B will then verify whether m′ is the element from a space MR. If this is not the case, the signature will be rejected. If this is the case, the message m will be retrieved by calculating m=R−1(m′).
It becomes evident from the above representation that modular exponentiation is required in a variety of places. In particular for RSA encryption in equation (2) and for RSA signature generation in equation (3), the secret key d is used for calculation.
Since the secret key—just like the public key—may take on considerable lengths, such as 1024 or 2048 bits, in typical RSA systems, modular exponentiation is a relatively extensive calculation.
To be able to calculate modular exponentiation more rapidly, it is known to employ the so-called Chinese remainder theorem (CRT) described in paragraph 2.120 of the above-designated specialist book. For RSA systems the Garner algorithm, which is also described in the above-described specialist book, chapter 14.5.2, is especially preferred. The classic algorithm for the CRT typically requires a modular reduction with the module M, while this is not the case with the Garner algorithm. Instead, a “large” modular exponentiation is divided into two “small” modular exponentiations in the latter algorithm, the results of which are then united in accordance with the Chinese remainder theorem. Even though two exponentiations are required here, it is still better to calculate two “small” modular exponentiations than one “large” modular exponentiation.
For representing the RSA-CRT method using the Garner algorithm, reference is made to FIG. 3. In a block 100 the input parameters are set forth which all depend only on p and q as well as on key d, but not on the message m to be signed, for example. In a block 102, the output of the algorithm is represented as has been represented by means of equation (2) or equation (3).
A first modular auxiliary exponentiation (sp) is then calculated, in a block 104, from the input quantitys represented in block 100. By analogy therewith, a second modular auxiliary exponentiation (sq) is calculated in a block 106. The results of the first and second modular auxiliary exponentiations are then joined in accordance with the Chinese remainder theorem in a block 108 to obtain the result s=md mod n. Generally, the RSA-CRT method represented in FIG. 3 is about four times faster than direct calculation of the output represented in block 102, for example by means of the square-and-multiply algorithm.
Due to the efficiency of calculation, the RSA-CRT algorithm represented in FIG. 3 is in any case preferable to the square-and-multiply algorithm. However, the RSA-CRT algorithm has the disadvantage that it is very susceptible to cryptographic “attacks” in that the secret key d may be determined if an erroneous calculation of the RSA-CRT algorithm is evaluated accordingly. This fact has been described in “On the Importance of Eliminating Errors in Cryptographic Computations”, Boneh, De-Millo, Lipton, J. Cryptology (2001) 14, pp. 101 to 119. The document elaborates on the fact that in one implementation of the RSA method based on the Chinese remainder theorem (CRT), the secret signature key may be determined from a single erroneous RSA signature.
An erroneous RSA signature may be obtained by causing the software or hardware executing the algorithm to make errors, for example by exposing the crypto-processor to an mechanical or thermal load.
As countermeasures against such attacks based on hardware errors it has been proposed to verify the output of each calculation before same is output from the chip. Even though this additional verification step may downgrade the system behavior, mention is made that this additional verification is essential for security reasons.
The simplest manner of verification is to perform a counter-calculation with the public exponent e, the intention being to determine the following identity:(md)e=m mod n   (5)
However, this additional verification step is directly comparable to the actual signature and/or decryption step in terms of computing expenditure and therefore leads to a pronounced decrease in the system behavior, but provides a large amount of security.
However, another advantage is that the public key e is not available in common protocols, such as ZKA-lib, for example. ZKA-lip is a collection of specifications of the central credit committee governing which data is available. For the RSA-CRT method, only the input data given in block 100 of FIG. 3 is available. Here, the public key e is not part of the parameters preset in the ZKA-lib description. The exponent e would therefore have to be calculated with a lot of expenditure so as to be able to perform the “counter-calculation ” in accordance with equation (5). This would further reduce the performance of the signature chip card and is likely to lead to the effect that such algorithms stand no chance of catching on in the market due to their slow mode of operation.
A further method for verifying signatures created by RSA-CRT methods is described in the specialist publication by A. Shamir, “How to check modular Exponentiation”, Rump Session, Eurocrypt 97. This specialist publication suggests using a small random number r (for example, 32 bits) and to perform the following calculation instead of the calculation in block 104:sp′=md mod pr   (6)
The following calculation is performed instead of block 106:sp′=md mod qr   (7)
Subsequently, immediately after the calculations in accordance with the equations (6) and (7), the following verification calculations are performed:sp′ mod r=sq′ mod r   (8)
If the verification in accordance with equation (8) is true, sp and sq are obtained from the following equation (9):sp′ mod p=sp; sq′ mod q=sq   (9)
From the values sp and sq obtained through equation (9), the calculation represented in block 108 in FIG. 3 is then performed so as to put combine the total result s by means of the Chinese remainder theorem from the modular auxiliary exponentiations.
This method has the disadvantage that only the auxiliary parameter r and the intermediate results sp′ and sq′ are used for verification, the verification not leading to the suppression of an output value if a cryptographic attack has taken place which possibly has not affected the intermediate results sp′, sq′ or the parameter r, but subsequently leading to a hardware error, for example in the steps given in equation (9) and in the final combining of the algorithm, which hardware error may be used to spy out the secret key d without permission.
In addition, the cited specialist publication by Boneh et al. proposes, for example as a countermeasure for protecting the Fiat-Shamir scheme, warding off any occurring register errors, while the processor is waiting for an external response, by employing error detection bits for protecting the internal memory of a processor. Further measures to protect RSA signatures are to introduce a randomness into the signature method. The randomness ensures that the signer never signs the same message twice. In addition, if the verifier is presented with an erroneous signature, it does not know the complete plain-text that has been signed.